【LeetCode 78】Subsets 子集

发表于 | 分类于

[LeetCode 78]Subsets 子集

Problem description:

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

问题描述:

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution:

Solution 1: 一个集合有n个元素，则其有2n的子集。

列出从0到2n-1的所有二进制，0表示不取对应元素，1表示取对应元素，即可得出所有子集。

1
2
3
4
5
6
7
8
9
	1	2	3	Subset
0	0	0	0	[]
1	0	0	1	3
2	0	1	0	2
3	0	1	1	23
4	1	0	0	1
5	1	0	1	13
6	1	1	0	12
7	1	1	1	123

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.ArrayList;
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        int count=pow(2,nums.length);
        for(int i=0;i<count;i++){
            char []bit=Integer.toBinaryString(i).toCharArray();
            ArrayList<Integer> temp=new ArrayList<Integer>();
            //从数组最后一位开始判断
            for(int j=bit.length-1,k=nums.length-1;j>=0;j--,k--){

                if(bit[j]=='1')
                 temp.add(nums[k]);

            }
            Collections.sort(temp);
            res.add(temp);
           temp=new ArrayList<Integer>();
        }
        return res;


    }
    public int pow(int i,int n){
        int res=1;
        for(int k=0;k<n;k++){
            res*=i;
        }
        return res;
    }
}

Solution 2：
深度优先算法，由于原集合每一个数字只有两种状态，要么存在，要么不存在，那么在构造子集时就有选择和不选择两种情况，所以可以构造一棵二叉树，左子树表示选择该元素，右子树表示不选择，最终的叶节点就是所有子集合，树的结构如下： 

1
2
3
4
5
6
7
8
9
10
		     []        
                 /          \        
                /            \     
               /              \
            [1]                []
         /       \           /    \
        /         \         /      \        
     [1 2]       [1]       [2]     []
    /     \     /   \     /   \    / \
[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        ArrayList<Integer> temp=new ArrayList<Integer>();
        getSubList(nums,res,temp,0);
        return res;
    }
    public void getSubList(int []nums,List<List<Integer>> res,ArrayList<Integer> temp,int pos){
        res.add(new ArrayList(temp));//注意要new一个ArrayList对象
        for(int i=pos;i<nums.length;i++){
            temp.add(nums[i]);//选择元素nums[i]
            getSubList(nums,res,temp,i+1);//下一个元素
            temp.remove(temp.size()-1);//不选择nums[i]

    }
  }
}
Thanks!